package com.sakura.动态规划;

import java.util.Arrays;

public class Code96_不同的二叉搜索树 {

    public static void main(String[] args) {
        System.out.println(new Code96_不同的二叉搜索树().numTrees3(4));
    }

    public int numTrees1(int n) {
        if (n == 0 || n == 1) return 1;
        int ans = 0;
        for (int k = 0; k < n; k++) {
            // 左子树 * 右子树的结果
            ans += numTrees1(k) * numTrees1(n - k - 1);
        }
        return ans;
    }

    // 记忆化搜索
    public int numTrees2(int n) {
        int[] dp = new int[n + 1];
        return f1(n, dp);
    }

    private int f1(int n, int[] dp) {
        if (n == 0 || n == 1) return 1;
        if (dp[n] != 0) return dp[n];
        int ans = 0;
        for (int k = 0; k < n; k++) {
            ans += f1(k, dp) * f1(n - k - 1, dp);
        }
        dp[n] = ans;
        return ans;
    }

    // 动态规划
    public int numTrees3(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int ans = 0;
            for (int k = 0; k < i; k++) {
                ans += dp[k] * dp[i - k - 1];
            }
            dp[i] = ans;
        }
        return dp[n];
    }
}
